home *** CD-ROM | disk | FTP | other *** search
- Path: garden.csc.calpoly.edu!not-for-mail
- From: dstubbs@garden.csc.calpoly.edu (Dan Stubbs)
- Newsgroups: comp.lang.c
- Subject: Re: Sorting algorithm - In search of
- Date: 4 Mar 1996 20:18:49 -0800
- Organization: Cal Poly, San Luis Obispo
- Message-ID: <4hgfb9$8b7@garden.csc.calpoly.edu>
- References: <4h4jmq$3bh@news.cis.nctu.edu.tw> <4hat5g$bdq@fohnix.metronet.com> <4hd557$ai2@garden.csc.calpoly.edu> <4hff0pINN9f4@keats.ugrad.cs.ubc.ca>
- NNTP-Posting-User: dstubbs@garden.csc.calpoly.edu
-
- In article <4hff0pINN9f4@keats.ugrad.cs.ubc.ca>,
- Kazimir Kylheku <c2a192@ugrad.cs.ubc.ca> wrote:
- >
- >Who says that qsort() necessarily uses the quicksort agorithm?
- >
- Nobody. qsort can, of course, be implemented using any sort algorithm
- However, can you name a single distributed C library that implements
- qsort using an algorithm other than some version of quicksort?
-
- > >Further, some implementations of qsort do not perform well for certain
- >
- >You surely mean ``of quicksort''. qsort() is a standard C function that is
- >unrelated to the quicksort algorithm.
- >
-
- No, I mean that some implementations of qsort do not perform well for
- certain initial data distributions. For the details of several examples
- see Bentley, "Engineering a Sort Function," Software--Practice & Experience,
- Nov., 93.
-
- >Does the standard require that qsort() be an incarnation of Hoare's quicksort?
- >
- No, it certainly does not. However, once again, can you name a single
- C library in which the implementation of qsort is based on an algorithm
- other than quicksort?
-
- >You can't test qsort(), you can only test particular implementations of it.
-
- We certainly agree.
-
- A further note. In Bentley's paper referenced above it states, "In fact,
- among a dozen different Unix libraries we found no qsort that could not
- easily be driven to quadratic behavior; all wer derived from the Seventh
- Edition Unix System (from Bell Labs) or from the 1983 Berkeley function."
-
- Thus, although by no means required to do so, these dozen systems implemented
- qsort with some variation of quicksort. And, in every case there were
- initial data distributions that gave serious performance problems.
-
-